/**
 * 给定一个数组A，每次询问问：[L, R]之间能组成多少对？
 * 成对的条件就是两个位置的元素值相等即可
 * N在1E5，莫队算法模板题，记录全局Cnt数组
 * 当某个Cnt[c]加成了偶数，即多了一对
 * 减成了奇数，即少了一对。
*/
#include <bits/stdc++.h>
using namespace std;

#include <bits/extc++.h>
using namespace __gnu_pbds;

using llt = long long;

struct mo_t{ // 莫队算法无修改, 依次调用input(),run(),output()

struct query_t{
    int s;
    int e;
    int idx;
    bool operator < (const query_t & b) const {
        int ln = s / block_size();
        int rn = b.s / block_size();
        if(ln != rn) return ln < rn;
        return e < b.e;
    }
};

using value_t = int;
using answer_t = int;

vector<value_t> data;      // 原始数组
vector<query_t> questions; // 问题
vector<answer_t> ans;      // 答案
vector<int> Cnt;
int moans;

int curLeft, curRight;

static int block_size() {
    static int const BLOCK_SIZE = 300;
    return BLOCK_SIZE;
}

void init(){
    ans.assign(questions.size(), 0);
    sort(questions.begin(), questions.end());

    curLeft = 1; curRight = 0;

    // assert(0);
    Cnt.assign(data.size() + 1, moans = 0);
}

void insert(int idx){
    // assert(0);
    if(0 == ++Cnt[data[idx]] % 2) ++moans;
}

void remove(int idx){
    // assert(0);
    if(1 & --Cnt[data[idx]]) --moans;
}

answer_t answer(){
    // assert(0);
    return moans;
}

void input(){
    // assert(0);
    int n; cin >> n;
    data.assign(n + 1, 0);
    for(int i=1;i<=n;++i) cin >> data[i];
    int q; cin >> q;
    questions.assign(q, {});
    int k = 0;
    for(auto & q : questions){
        cin >> q.s >> q.e;
        q.idx = k++;
    }
    return;
}

void run(){
    init();

    for(const auto & q : questions){
        while(curRight < q.e) insert(++curRight);
        while(curLeft > q.s) insert(--curLeft);
        while(curRight > q.e) remove(curRight--);
        while(curLeft < q.s) remove(curLeft++);
        ans[q.idx] = answer();
    }
}

void output(){
    for(auto i : ans) cout << i << "\n";
    // cout << endl;
}

};

mo_t Mo;

int main(){
#ifndef ONLINE_JUDGE
    freopen("z.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(0);
	Mo.input();
    Mo.run();
    Mo.output();
    return 0;
}